/*
 *
 * BEGIN THE SELLIE CODE!
 *
 */
#include <iostream>
#include <exception>
#include <queue>

using namespace std;

typedef exception UnderflowException;
typedef exception DuplicateItemException;
typedef exception ItemNotFoundException;

template< class Comparable>
class BinarySearchTree;

template <class Comparable>
class BinaryNode
{
	public:
	Comparable  element;
	private:
	BinaryNode *left;
	BinaryNode *right;
	int size;
	
	BinaryNode( const Comparable & theElement, BinaryNode *lt,
			BinaryNode *rt, int sz = 1 )
		: element( theElement ), left( lt ), right( rt ), size( sz ) { }

	friend class BinarySearchTree<Comparable>;
};

template <class Comparable>
class BinarySearchTree
{
	public:
		typedef BinaryNode<Comparable> Node;

		BinarySearchTree( ) : root( NULL ) { } // Construct the tree.
		~BinarySearchTree( ){ makeEmpty( ); } // Destructor for the tree.

		//MY METHODS
		Node* find(const Comparable& o, Node* n){
			if(n->element == o){
				return n;
			}
			else if(n->element > o && n->left!= NULL){
				return find(o, n->left);
			}
			else if(n->element < o && n->left != NULL){
				return find(o, n->right);
			}
			else{
				cerr << '\t' << "Not found... :(" << endl;
				throw ItemNotFoundException();
			}

		}

		Node* find(const Comparable& o){
			return find(o, root);
		}

		int nu_leaves(Node* n){
			if(n->left == NULL && n->right == NULL)
				return 1;
			else{
				if(n->left == NULL)
					return nu_leaves(n->right);
				else if(n->right == NULL)
					return nu_leaves(n->left);
				else
					return nu_leaves(n->left) + nu_leaves(n->right);
			}
		}

		int nu_leaves(){
			return nu_leaves(root);
		}

		bool in_order(Node* n){
			if(n->left == NULL && n->right == NULL)
				return true;
			else{
				if(n->left == NULL){
					bool good = (n->right->element) > n->element;
					return good && in_order(n->right);
				}
				else if(n->right == NULL){
					bool good = n->left->element < n->element;
					return good && in_order(n->left);
				}
				else{
					bool good = n->left->element < n->element && n->right->element > n->element;
					return good && in_order(n->left) && in_order(n->right);
				}
			}
		}

		bool in_order(){
			return in_order(root);
		}

		int countNodesWithOneChild(Node* n){
			if(n->left == NULL && n->right == NULL)
				return 0;
			else{
				if(n->left == NULL)
					return 1 + countNodesWithOneChild(n->right);
				else if(n->right == NULL)
					return 1 + countNodesWithOneChild(n->left);
				else
					return countNodesWithOneChild(n->left) + countNodesWithOneChild(n->right);
			}
		}

		int countNodesWithOneChild(){
			return countNodesWithOneChild(root);
		}

		int countDepth(Node* n, int d){
			int ld = 0;
			int rd = 0;
			if(n->left != NULL)
				ld = countDepth(n->left, d+1);
			if(n->right != NULL)
				rd = countDepth(n->right, d+1);
			return d + ld + rd;
		}
		int average_node_depth(){
			return countDepth(root, 0)/treeSize(root);
		}


		// #3
		
		void level_print(Node* n){
			queue<Node*> q;
			q.push(root);
			while(!(q.empty())){
				cout << q.front()->element << " ";
				if(q.front()->left != NULL)
					q.push(q.front()->left);
				if(q.front()->right != NULL)
					q.push(q.front()->right);
				q.pop();
			}
		}

		void level_print(){
			level_print(root);
			cout << endl;
		}

		void iop(Node* n){
			if(n->left != NULL)
				iop(n->left);
			cout << n->element << " ";
			if(n->right != NULL)
				iop(n->right);

		}

		void iop(){
			iop(root);
		}

		bool isEmpty( ) const { return root == NULL;}
		void makeEmpty( ) { makeEmpty( root ); }
		void insert( const Comparable & x ) { insert( x, root ); }

	private:
		Node * root;

		int treeSize( Node *t ) const { return t == NULL ? 0 : t->size; }
		Comparable const * elementAt( Node *t ) const;
		void insert( const Comparable & x, Node * & t );
		void makeEmpty( Node * & t ) const;
		Node * clone( Node *t ) const;

};



template <class Comparable>
Comparable const * BinarySearchTree<Comparable>::elementAt( Node *t ) const
{
	if( t == NULL )
		return NULL;
	else
		return &(t->element);
}



	template <class Comparable>
void BinarySearchTree<Comparable>::insert( const Comparable & x, Node * & t )
{
	if( t == NULL )
		t = new Node( x, NULL, NULL, 0 );
	else if( x < t->element )
		insert( x, t->left );
	else if( t->element < x )
		insert( x, t->right );
	else
		throw DuplicateItemException( );

	t->size++;
}



template <class Comparable>
void BinarySearchTree<Comparable>::makeEmpty( Node * & t ) const
{
	if( t != NULL )
	{
		makeEmpty( t->left );
		makeEmpty( t->right );
		delete t;
		t = NULL;
	}
}

/*
 *
 * END THE SELLIE CODE!
 *
 */

int main(){
	//I'll have something to put here eventually
	BinarySearchTree<int> bst;
	bst.insert(20);
	bst.insert(53);
	bst.insert(14);
	bst.insert(1);
	bst.insert(15);
	bst.insert(63);
	bst.iop();
	cout << boolalpha << bst.in_order() << endl;

	cout << bst.nu_leaves() << " " << bst.countNodesWithOneChild() << " " << bst.average_node_depth() << endl;

	BinaryNode<int>* found = bst.find(14);
	cout << found->element << endl;


	//Quesion 1
	

}
